<head>
    <meta charset="UTF-8">
<title>算法提高 金陵十三钗</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <!--[if gte mso 9]><xml>
<w:WordDocument>
<w:View>Normal</w:View>
<w:Zoom>0</w:Zoom>
<w:PunctuationKerning />
<w:DrawingGridVerticalSpacing>7.8 磅</w:DrawingGridVerticalSpacing>
<w:DisplayHorizontalDrawingGridEvery>0</w:DisplayHorizontalDrawingGridEvery>
<w:DisplayVerticalDrawingGridEvery>2</w:DisplayVerticalDrawingGridEvery>
<w:ValidateAgainstSchemas />
<w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid>
<w:IgnoreMixedContent>false</w:IgnoreMixedContent>
<w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText>
<w:Compatibility>
<w:SpaceForUL />
<w:BalanceSingleByteDoubleByteWidth />
<w:DoNotLeaveBackslashAlone />
<w:ULTrailSpace />
<w:DoNotExpandShiftReturn />
<w:AdjustLineHeightInTable />
<w:BreakWrappedTables />
<w:SnapToGridInCell />
<w:WrapTextWithPunct />
<w:UseAsianBreakRules />
<w:DontGrowAutofit />
<w:UseFELayout />
</w:Compatibility>
<w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel>
</w:WordDocument>
</xml><![endif]--><!--[if gte mso 9]><xml>
<w:LatentStyles DefLockedState="false" LatentStyleCount="156">
</w:LatentStyles>
</xml><![endif]--><!--[if gte mso 10]>
<style>
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:普通表格;
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-parent:"";
mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
mso-para-margin:0cm;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-ansi-language:#0400;
mso-fareast-language:#0400;
mso-bidi-language:#0400;}
</style>
<![endif]-->
<p align="center" style="text-align: center;" class="MsoNormal"><span style="font-family: 宋体;">金陵十三钗</span></p>
<p class="MsoNormal"><span style="font-family: 宋体;">本题难度：难</span></p>
<p class="MsoNormal"><span style="font-family: 宋体;">本题占分比例：</span><span lang="EN-US">5%</span></p>
<p class="MsoNormal"><span style="font-family: 宋体;">【问题描述】</span></p>
<p class="MsoNormal"><span lang="EN-US"><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span><span style="font-family: 宋体;">在电影《金陵十三钗》中有十二个秦淮河的女人要自我牺牲代替十二个女学生去赴日本人的死亡宴会。为了不让日本人发现，自然需要一番乔装打扮。但由于天生材质的原因，每个人和每个人之间的相似度是不同的。由于我们这是编程题，因此情况就变成了金陵</span><span lang="EN-US">n</span><span style="font-family: 宋体;">钗。给出</span><span lang="EN-US">n</span><span style="font-family: 宋体;">个女人和</span><span lang="EN-US">n</span><span style="font-family: 宋体;">个学生的相似度矩阵，求她们之间的匹配所能获得的最大相似度。</span></p>
<p class="MsoNormal"><span lang="EN-US"><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span><span style="font-family: 宋体;">所谓相似度矩阵是一个</span><span lang="EN-US">n*n</span><span style="font-family: 宋体;">的二维数组</span><span lang="EN-US">like[i][j]</span><span style="font-family: 宋体;">。其中</span><span lang="EN-US">i,j</span><span style="font-family: 宋体;">分别为女人的编号和学生的编号，皆从</span><span lang="EN-US">0</span><span style="font-family: 宋体;">到</span><span lang="EN-US">n-1</span><span style="font-family: 宋体;">编号。</span><span lang="EN-US">like[i][j]</span><span style="font-family: 宋体;">是一个</span><span lang="EN-US">0</span><span style="font-family: 宋体;">到</span><span lang="EN-US">100</span><span style="font-family: 宋体;">的整数值，表示第</span><span lang="EN-US">i</span><span style="font-family: 宋体;">个女人和第</span><span lang="EN-US">j</span><span style="font-family: 宋体;">个学生的相似度，值越大相似度越大，比如</span><span lang="EN-US">0</span><span style="font-family: 宋体;">表示完全不相似，</span><span lang="EN-US">100</span><span style="font-family: 宋体;">表示百分之百一样。每个女人都需要找一个自己代替的女学生。</span></p>
<p style="text-indent: 21pt;" class="MsoNormal"><span style="font-family: 宋体;">最终要使两边一一配对，形成一个匹配。请编程找到一种匹配方案，使各对女人和女学生之间的相似度之和最大。</span></p>
<p class="MsoNormal"><span lang="EN-US">&nbsp;</span></p>
<p class="MsoNormal"><span style="font-family: 宋体;">【输入格式】</span></p>
<p class="MsoNormal"><span lang="EN-US"><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span><span style="font-family: 宋体;">第一行一个正整数</span><span lang="EN-US">n</span><span style="font-family: 宋体;">表示有</span><span lang="EN-US">n</span><span style="font-family: 宋体;">个秦淮河女人和</span><span lang="EN-US">n</span><span style="font-family: 宋体;">个女学生</span></p>
<p class="MsoNormal"><span lang="EN-US"><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span><span style="font-family: 宋体;">接下来</span><span lang="EN-US">n</span><span style="font-family: 宋体;">行给出相似度，每行</span><span lang="EN-US">n</span><span style="font-family: 宋体;">个</span><span lang="EN-US">0</span><span style="font-family: 宋体;">到</span><span lang="EN-US">100</span><span style="font-family: 宋体;">的整数，依次对应二维矩阵的</span><span lang="EN-US">n</span><span style="font-family: 宋体;">行</span><span lang="EN-US">n</span><span style="font-family: 宋体;">列。</span></p>
<p class="MsoNormal"><span lang="EN-US">&nbsp;</span></p>
<p class="MsoNormal"><span style="font-family: 宋体;">【输出格式】</span></p>
<p class="MsoNormal"><span lang="EN-US"><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span><span style="font-family: 宋体;">仅一行，一个整数，表示可获得的最大相似度。</span></p>
<p class="MsoNormal"><span lang="EN-US">&nbsp;</span></p>
<p class="MsoNormal"><span style="font-family: 宋体;">【样例输入】</span></p>
<p class="MsoNormal"><span lang="EN-US">4</span></p>
<p class="MsoNormal"><span lang="EN-US">97 91 68 14</span></p>
<p class="MsoNormal"><span lang="EN-US">8 33 27 92</span></p>
<p class="MsoNormal"><span lang="EN-US">36 32 98 53</span></p>
<p class="MsoNormal"><span lang="EN-US">73 7 17 82</span></p>
<p class="MsoNormal"><span lang="EN-US">&nbsp;</span></p>
<p class="MsoNormal"><span style="font-family: 宋体;">【样例输出】</span></p>
<p class="MsoNormal"><span lang="EN-US">354</span></p>
<p class="MsoNormal"><span lang="EN-US">&nbsp;</span></p>
<p class="MsoNormal"><span style="font-family: 宋体;">【数据规模】</span></p>
<p class="MsoNormal"><span lang="EN-US"><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span><span style="font-family: 宋体;">对于</span><span lang="EN-US">70%</span><span style="font-family: 宋体;">的数据，</span><span lang="EN-US">n&lt;=10</span></p>
<p class="MsoNormal"><span lang="EN-US"><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span><span style="font-family: 宋体;">对于</span><span lang="EN-US">100%</span><span style="font-family: 宋体;">的数据，</span><span lang="EN-US">n&lt;=13</span></p>
<p class="MsoNormal"><span lang="EN-US">&nbsp;</span></p>
<p class="MsoNormal"><span style="font-family: 宋体;">【样例说明】</span></p>
<p class="MsoNormal"><span style="font-family: 宋体;">最大相似度为</span><span lang="EN-US">91+92+93+73=354</span></p>
<p class="MsoNormal"><span lang="EN-US">&nbsp;</span></p>